package 数组题目.前缀和与差分;

//除自身以外数组的乘积
//https://leetcode.cn/problems/product-of-array-except-self/
class 除自身以外数组的乘积 {
    public int[] productExceptSelf(int[] nums) {
        int[] prefixNums = new int[nums.length];
        int[] suffixNums = new int[nums.length];
        prefixNums[0] = nums[0];
        suffixNums[nums.length - 1] = nums[nums.length - 1];
        for (int i = 1, j = nums.length - 2; i < nums.length; i++, j--) {
            //前缀积
            prefixNums[i] = nums[i] * prefixNums[i - 1];
            //后缀积
            suffixNums[j] = suffixNums[j + 1] * nums[j];
        }
        nums[0] = suffixNums[1];
        nums[nums.length - 1] = prefixNums[nums.length - 2];
        for (int i = 1; i < nums.length - 1; i++) {
            nums[i] = prefixNums[i - 1] * suffixNums[i + 1];
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        System.out.println(new 除自身以外数组的乘积().productExceptSelf(nums));
    }
}
